Leetcode 946. Validate Stack Sequences 验证栈序列

Posted on | In

946. Validate Stack Sequences

题目描述

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

示例

示例1

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例2

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

解答

这道题很简单，把pushed数组里面的每个数字入栈，然后当push的值和popped里面的第一个未处理的值相等的时候，就进入循环，将popped数组里面的值从栈中移除。

最后判断popped数组里面的值是否处理完。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> mystack;
        int i = 0;

        for (auto &s : pushed) {
        	mystack.push(s);

        	while (!mystack.empty() && mystack.top() == popped[i]) {
        		i ++;
        		
        		mystack.pop();
        	}

        }
        if (mystack.empty() && i == popped.size()){
        	return true;
        }
        return false;
    }
};